package leetcode_数组.统计数组中的元素;

import java.util.ArrayList;
import java.util.List;

// 找到所有数组中消失的数字
// 方法：给数组做标记
public class _448 {
    public static void main(String[] args) {
        int[] ints = {4, 3, 2, 7, 8, 2, 3, 1};
        System.out.println(findDisappearedNumbers1(ints));
    }

    public static List<Integer> findDisappearedNumbers(int[] nums) {
        int[] ints = new int[nums.length + 1];
        List<Integer> ans = new ArrayList<Integer>();
        for (int num : nums) {
            ints[num]++;
        }
        for (int i = 1; i < ints.length; i++) {
            if (ints[i] == 0) {
                ans.add(i);
            }
        }
        return ans;
    }

    // 不使用额外空间
    /*
    如果该数字存在，则索引所对应的数是负数
    数字跟索引有对应关系
     */
    public static List<Integer> findDisappearedNumbers1(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int newIndex = Math.abs(nums[i]) - 1;
            if (nums[newIndex] > 0) {
                nums[newIndex] *= -1;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                ans.add(i + 1);
            }
        }
        return ans;
    }

}
